1. Field of the Invention
The present invention relates to apparatus used in computer systems to determine which of a plurality of devices which share a bus is to have access to the bus at a given instant and more particularly to apparatus in which access is determined by assigning priorities to the devices.
2. Description of the Prior Art
When a plurality of devices in a computer system shares a bus, the computer system must include some way of preventing more than one of the devices from using the bus at once. One technique used in the prior art is to assign each device a static priority; if a device with a high priority and one with a low priority both attempt to access the bus, the low priority wins. One way of assigning priorities, shown in FIG. 5, is by position. FIG. 5 is a conceptual drawing of a static daisy chain 501. A set of nodes 503, each one of which may provide access to a bus 504 for one or more devices, is arranged in daisy chain fashion, with a priority bus (PB) 507 connecting adjacent members of the chain. The leftmost node 503(1) in the chain has the highest priority, and each succeeding node 503 has a lower priority than the one preceding it. Thus, if node 503(1) and another node 503(a) request access simultaneously, node 503(1) receives the access. For purposes of the present discussion, daisy chain 501 may be regarded as having a static "anchor" 505 which marks the point from which all priorities are determined. While static daisy chain 501 successfully determines which of the nodes 503 will have access to the bus at a given time and has the important advantage that the node 503 having priority gains immediate access to bus 504, it does not prevent higher-priority devices from "hogging" bus 504 and denying access to the bus to lower-priority devices. For example, if node 503(1) requests access to the bus on each bus cycle, no other node 503 in chain 501 will ever gain access to the bus 504.
The "hogging" problem may be eliminated if each node is guaranteed a turn at the bus. One way of doing this is disclosed in U.S. Pat. No. 4,342,995, Data Network Employing a Single Transmission Bus for Overlapping Data Transmission and Acknowledgement Signals, inventor George T. Shima, issued Aug. 3, 1982. In the system disclosed in that patent, the nodes are daisy-chained together in a loop and a pulse is circulated around the loop. When a node which has a pending bus access request receives the pulse, it gains access to the bus. When the node is finished, it provides the pulse to the next node. If the node which receives the pulse does not wish to access the bus, it holds the pulse for a short time and then passes it to the next node in the chain. While the system of Shima guarantees that none of the nodes will "hog" the bus, it is extremely inefficient in a situation in which one of the nodes uses the bus much more frequently than the other nodes. Once a node in the system of Shima has finished using the bus, it must always wait to begin its next bus access until the pulse has been passed to all of the other nodes on the chain, even though none of the other nodes has a bus access request pending.
What is needed, and what is provided by the invention which is the subject of the present application, is bus priority apparatus which neither permits a single node to "hog" the bus nor requires a node to wait to gain access to the bus when no other node has a request pending.